﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
using System.Drawing;
using System.Threading;

namespace IA2MazeSolver
{
    public class MazeSolver
    {
        private Maze Labirinto;

        public List<Individuo> Populacao;

        private static readonly Random RandomGen = new Random();

        private static readonly Random GetRandom = new Random();
        private static readonly object syncLock = new object();
        public static int GetRandomNumber(int min, int max)
        {
            lock (syncLock)
            { // synchronize
                return GetRandom.Next(min, max);
            }
        }

        private static int PESO_COLISAO = 50;
        private static int PESO_SAIDA = 50;
        private static int PESO_REPETICAO = 20;
        private static int PESO_COORD = 50;

        public MazeSolver(Maze labirinto)
        {
            this.Labirinto = labirinto;
            this.Populacao = new List<Individuo>();
        }

        #region Populacao

        public void GerarPopulacao(int quantidade, int caminho_minimo, int caminho_maximo)
        {
            this.Populacao.Clear();

            //Random rndSize = new Random(DateTime.Now.Millisecond);

            if ( (quantidade % 2) == 1)
            {
                quantidade++;
            }

            Direcao[] Direcoes = new Direcao[] {
                Direcao.Leste,
                Direcao.Norte,
                Direcao.Oeste/*,
                Direcao.Sul*/
            };

            //this.Populacao.Add(MazeHelper.StringToByte("0101010000010000100101101001000000000101000000110001"));

            int MIN = 0;
            int MAX = Direcoes.Length;

            for (int i = 0; i < quantidade; i++)
            {
                int caminhoSize = GetRandomNumber(caminho_minimo, caminho_maximo);
                if ((caminhoSize % 2) == 1)
                {
                    caminhoSize++;
                }

                byte[] caminho = new byte[caminhoSize];
                caminho[0] = 0;
                caminho[1] = 0;
                caminho[2] = 0;
                caminho[3] = 1;
                caminho[4] = 0;
                caminho[5] = 1;

                //Random rndDir = new Random();
                int j = 0;
                for (j = 6; j < caminhoSize-8; j += 2)
                {
                    //int idxDir = rndDir.Next(MIN, MAX);
                    int idxDir = GetRandomNumber(MIN, MAX);
                    caminho[j] = Direcoes[idxDir].PontoA;
                    caminho[j+1] = Direcoes[idxDir].PontoB;
                }

                caminho[j] = 1;
                caminho[j + 1] = 1;
                caminho[j + 2] = 0;
                caminho[j + 3] = 0;
                caminho[j + 4] = 0;
                caminho[j + 5] = 1;
                caminho[j + 6] = 0;
                caminho[j + 7] = 0;
                this.Populacao.Add(new Individuo(caminho));
            }
        }

        #endregion

        #region CrossOver

        public List<Individuo> AplicaCrossOver(List<Individuo> _Lista, int fatias)
        {
            List<Individuo> Lista = _Lista.ToList();
            
            Random rnd = new Random();

            List<Individuo> Filhos = new List<Individuo>();
            int size = Lista.Count();

            for (int i = 0; i < size; i += 2)
            {
                Individuo PaiA = Lista[i];
                Individuo PaiB = Lista[i + 1];
                Individuo FilhoA, FilhoB;

                this.CrossOver(PaiA, PaiB, fatias, out FilhoA, out FilhoB);

                Filhos.Add(FilhoA);
                Filhos.Add(FilhoB);
            }

            return Filhos;
        }

        public byte[] CrossVet(byte[] a, byte[] b, int Corte)
        {
            byte[] x = new byte[a.Length];
            
            int i = 0;
            int c = 0;
            int sentido = 0;

            while (i < a.Length)
            {
                if (sentido == 0)
                {
                    x[i] = a[i];

                }
                else
                {
                    if (i < b.Length)
                    {
                        x[i] = b[i];
                    }
                    else
                    {
                        x[i] = a[i];
                    }
                }

                c++;

                if (c >= Corte)
                {
                    if (sentido == 0)
                    {
                        sentido = 1;
                    }
                    else
                    {
                        sentido = 0;
                    }
                    c = 0;
                }

                i++;
            }

            return x;
        }

        public void CrossOver(Individuo PaiA, Individuo PaiB, int fatias, out Individuo FilhoA, out Individuo FilhoB)
        {
            int PaiALength = PaiA.Data.Length;
            int PaiBLength = PaiB.Data.Length;

            double Maior = Math.Max(PaiA.Data.Length, PaiB.Data.Length);

            int Corte = Convert.ToInt32(Math.Ceiling(Maior / fatias));
            if (Corte % 2 == 1)
            {
                Corte++;
            }

            byte[] filhoA = this.CrossVet(PaiA.Data, PaiB.Data, Corte);
            byte[] filhoB = this.CrossVet(PaiB.Data, PaiA.Data, Corte);

            FilhoA = new Individuo(filhoA);
            FilhoB = new Individuo(filhoB);
        }

        #endregion

        #region Mutacao

        public void AplicarMutacao(List<Individuo> Lista, int PorCento)
        {
            Random rnd = new Random(DateTime.Now.Millisecond);

            int size = Lista.Count();
            int qtde = Convert.ToInt32(Math.Round(size * (PorCento / 100d), 0));

            for (int i = 0; i < qtde; i++)
			{
                int idx = rnd.Next(0, size);
                this.Mutacao(Lista[idx]);
            }
        }

        private void Mutacao(Individuo individuo)
        {
            //Random rnd = new Random(DateTime.Now.Millisecond);
            //int indice = rnd.Next(0, individuo.Data.Length - 1);
            int indice = GetRandomNumber(0, individuo.Data.Length);

            if (indice % 2 == 1)
            {
                indice--;
            }

            if (individuo.Data[indice] == 0)
            {
                individuo.Data[indice] = 1;
            }
            else
            {
                individuo.Data[indice] = 0;
            }

            indice++;

            if (individuo.Data[indice] == 0)
            {
                individuo.Data[indice] = 1;
            }
            else
            {
                individuo.Data[indice] = 0;
            }
        }

        #endregion

        #region Fitness

        public Individuo CalculaFitness()
        {
            int PopulacaoSize = this.Populacao.Count();
            if (PopulacaoSize % 2 == 1)
            {
                //throw new Exception("Populacao fora do padrão aceito");
            }

            int fitness = this.AvaliarIndividuo(this.Populacao[0]);
            Individuo menor = this.Populacao[0];

            for (int i = 0; i < PopulacaoSize; i++)
            {
                fitness = this.AvaliarIndividuo(this.Populacao[i]);
                this.Populacao[i].Fitness = fitness;
                if (fitness < menor.Fitness)
                {
                    menor = this.Populacao[i];
                }
            }

            return menor;
        }

        #endregion

        #region Selecao

        public List<Individuo> SelecaoTorneio()
        {
            List<Individuo> Selecao = new List<Individuo>();

            int max = this.Populacao.Count();
            int c = 0;
            int temp = 0;

            for (int i = 0; i < max; i++)
            {
                int a = GetRandomNumber(0, max);
                int b = GetRandomNumber(0, max);

                while (b == a) { b = GetRandomNumber(0, max); }

                if (this.Populacao[a].Fitness <= this.Populacao[b].Fitness)
                {
                    temp = a;
                }
                else
                {
                    temp = b;
                }
                if (i > 0)
                {
                    while (c == temp) { temp = GetRandomNumber(0, max); }
                }

                c = temp;
                Selecao.Add(this.Populacao[c]);
            }

            return Selecao;
        }

        public List<Individuo> SelecaoRanking()
        {
            List<Individuo> Selecao;

            Selecao = this.Populacao.ToList();
            Selecao.Sort();

            return Selecao;
        }

        public List<Individuo> SelecaoRoleta()
        {
            Random rng = new Random();
            double[] cumulativeFitnesses = new double[this.Populacao.Count()];
            cumulativeFitnesses[0] = this.Populacao[0].Fitness;
            for (int i = 1; i < this.Populacao.Count(); i++)
            {
                double fitness = this.Populacao[i].Fitness;
                cumulativeFitnesses[i] = cumulativeFitnesses[i - 1] + fitness;
            }

            List<Individuo> Selecao = new List<Individuo>();
            for (int i = 0; i < this.Populacao.Count(); i++)
            {
                double x = rng.NextDouble();
                double randomFitness = x * cumulativeFitnesses[cumulativeFitnesses.Length - 1];
                int index = Array.BinarySearch(cumulativeFitnesses, randomFitness);
                if (index < 0)
                {
                    index = Math.Abs(index + 1);
                }
                //Inverto!
                index = this.Populacao.Count() - index - 1;
                Selecao.Add(this.Populacao[index]);
            }
            return Selecao;
        }

        #endregion

        #region Elitismo

        public List<Individuo> Elitismo(List<Individuo> Populacao)
        {
            Populacao.Sort();

            int Total = Populacao.Count() / 2;

            List<Individuo> NovaPopulacao = Populacao.GetRange(0, Total);

            return NovaPopulacao;
        }

        #endregion

        #region Individuo
        
        public int AvaliarIndividuo(Individuo individuo)
        {
            byte[] caminho = individuo.Data;

            MazeData DataToWork = new MazeData(this.Labirinto.Data, this.Labirinto.DrawWidth, this.Labirinto.DrawHeight);

            //Point ponto = new Point(this.Labirinto.StartPoint.X, this.Labirinto.StartPoint.Y);
            Point ponto = new Point(this.Labirinto.StartPoint.X-1, this.Labirinto.StartPoint.Y);

            Point pontoDeParada = this.Labirinto.ToMeasureDraw(ponto);

            DataToWork.AddValue(pontoDeParada, 1);

            Point pontoTeste = new Point(0, 0);

            int colisoes = 0;
            int saidas = 0;
            int repeticoes = 0;
            int passos = 0;
            int suls = 0;
            int curve = 0;
            int bad = 0;

            int soma = 0;

            int i;
            for (i = 0; i < caminho.Length-2; i += 2)
            {
                Direcao Sentido = new Direcao(caminho[i], caminho[i + 1]);
                //EndPoint = new Point(ponto.X, ponto.Y);
                //Leste
                if (Sentido.Equals(Direcao.Leste))
                {
                    ponto = new Point(ponto.X + 1, ponto.Y);
                    pontoTeste = this.Labirinto.ToMeasureDraw(ponto);
                    pontoTeste.X -= 1;
                }

                //Norte
                if (Sentido.Equals(Direcao.Norte))
                {
                    ponto = new Point(ponto.X, ponto.Y - 1);
                    pontoTeste = this.Labirinto.ToMeasureDraw(ponto);
                    pontoTeste.Y += 1;
                }

                //Oeste
                if (Sentido.Equals(Direcao.Oeste))
                {
                    ponto = new Point(ponto.X - 1, ponto.Y);
                    pontoTeste = this.Labirinto.ToMeasureDraw(ponto);
                    pontoTeste.X += 1;
                }

                //Sul
                if (Sentido.Equals(Direcao.Sul))
                {
                    ponto = new Point(ponto.X, ponto.Y + 1);
                    pontoTeste = this.Labirinto.ToMeasureDraw(ponto);
                    pontoTeste.Y -= 1;
                    suls++;
                }

                pontoDeParada = this.Labirinto.ToMeasureDraw(ponto);

                int valor = DataToWork.GetValue(pontoTeste);

                if (valor == 0)
                {
                    colisoes++;
                }
                else if (valor == -1)
                {
                    saidas++;
                }

                int value = DataToWork.GetValue(pontoDeParada);
                if (
                    pontoDeParada.Equals(new Point(3, 15)) ||
                    pontoDeParada.Equals(new Point(5, 15)) ||
                    pontoDeParada.Equals(new Point(7, 15)) ||
                    pontoDeParada.Equals(new Point(7, 13)) ||
                    pontoDeParada.Equals(new Point(7, 11)) ||
                    pontoDeParada.Equals(new Point(7, 9)) ||
                    pontoDeParada.Equals(new Point(7, 7)) ||
                    pontoDeParada.Equals(new Point(5, 7)) ||
                    pontoDeParada.Equals(new Point(3, 7)) ||
                    pontoDeParada.Equals(new Point(1, 7)) ||
                    pontoDeParada.Equals(new Point(1, 5)) ||
                    pontoDeParada.Equals(new Point(3, 5)) ||
                    pontoDeParada.Equals(new Point(7, 5)) ||
                    pontoDeParada.Equals(new Point(9, 5)) ||
                    pontoDeParada.Equals(new Point(11, 5)) ||
                    pontoDeParada.Equals(new Point(11, 3)) ||
                    pontoDeParada.Equals(new Point(11, 1)) ||
                    pontoDeParada.Equals(new Point(13, 1)) ||
                    pontoDeParada.Equals(new Point(15, 1)) ||
                    pontoDeParada.Equals(new Point(17, 1))
                    )
                {
                    curve++;
                }

                if (
                    pontoDeParada.Equals(new Point(8, 11)) ||
                    pontoDeParada.Equals(new Point(9, 11)) ||
                    pontoDeParada.Equals(new Point(9, 9)) ||
                    pontoDeParada.Equals(new Point(8, 10)) ||
                    pontoDeParada.Equals(new Point(8, 9))
                    )
                {
                    //bad++;
                }

                if (value > 1)
                {
                    repeticoes++;
                }

                //8x-6y
                if (pontoDeParada.X > 8 && pontoDeParada.Y > 6)
                {
                    bad++;
                }
                

                DataToWork.AddValue(pontoDeParada, 1);

                passos++;
            }

            int colisoesPenalidade = 0;
            int penalidades = 0;
            if (colisoes > 0)
            {
                colisoesPenalidade = this.CalculaPenalidade(MazeSolver.PESO_COLISAO, colisoes);
                soma += colisoesPenalidade;
                penalidades += colisoes;
            }

            int saidasPenalidade = 0;
            if (saidas > 0)
            {
                saidasPenalidade = this.CalculaPenalidade(MazeSolver.PESO_SAIDA, saidas);
                soma += saidasPenalidade;
                penalidades += saidas;
            }

            int repeticoesPenalidade = 0;
            if (repeticoes > 0)
            {
                repeticoesPenalidade = this.CalculaPenalidade(MazeSolver.PESO_REPETICAO, repeticoes);
                soma += repeticoesPenalidade;
                penalidades += repeticoes;
            }

            int penalidadeChegada = 0;
            penalidadeChegada = this.CalculaPenalidadeChegada(ponto);
            soma += penalidadeChegada;

            if (!Direcao.Leste.Equals(new Direcao(caminho[i], caminho[i + 1])))
            {
                bad++;
            }

            int badPenalidade = 0;
            if (bad > 0)
            {
                badPenalidade = bad * 50;
                soma += badPenalidade;
            }

            int curveBonus = 0;
            if (curve > 0)
            {
                curveBonus = curve * 5;
                soma -= curveBonus;
                soma = Math.Max(soma, 0);
            }

            if (soma <= 0)
            {
                soma = Math.Max(colisoesPenalidade, 0);   
            }

            if (MazeDebug.Avaliacao)
            {
                MazeDebug.WriteLine(String.Format("Colisoes: {0} - {1}", colisoes, colisoesPenalidade));
                MazeDebug.WriteLine(String.Format("Saidas: {0} - {1}", saidas, saidasPenalidade));
                MazeDebug.WriteLine(String.Format("Repeticoes: {0} - {1}", repeticoes, repeticoesPenalidade));
                MazeDebug.WriteLine(String.Format("+Curve: {0} - {1}", curve, curveBonus));
                MazeDebug.WriteLine(String.Format("-Bad: {0} - {1}", bad, badPenalidade));
                MazeDebug.WriteLine(String.Format("Fim: {0}->{1} = {2}", ponto, this.Labirinto.EndPoint, penalidadeChegada));
                MazeDebug.WriteLine(String.Format("Total: {0} - {1}", penalidades, soma));
                MazeDebug.WriteLine("--------------------");
            }

            return soma;
        }

        private int CalculaPenalidade(int peso, int quantidade)
        {
            int resultado = quantidade * peso;

            return resultado;
        }

        private int CalculaPenalidadeChegada(Point EndPoint)
        {
            int total = 0;
            if (EndPoint.Equals(this.Labirinto.EndPoint))
            {
                total = 0;
            }
            else
            {
                double result = 0;
                int x = Math.Abs(this.Labirinto.EndPoint.X - EndPoint.X);
                result = this.CalculaPenalidade(MazeSolver.PESO_COORD, x);
                total += Convert.ToInt32(Math.Round(result, 0));

                int y = Math.Abs(this.Labirinto.EndPoint.Y - EndPoint.Y);
                result = this.CalculaPenalidade(MazeSolver.PESO_COORD, y);
                total += Convert.ToInt32(Math.Round(result, 0));
            }

            return total;
        }

        private int CalculaDistancia(Point EndPoint)
        {
            int total = 0;
            if (EndPoint.Equals(this.Labirinto.EndPoint))
            {
                total = 0;
            }
            else
            {
                int x = Math.Abs(this.Labirinto.EndPoint.X - EndPoint.X);
                int y = Math.Abs(this.Labirinto.EndPoint.Y - EndPoint.Y);

                total = x + y;
            }

            return total;
        }

        #endregion

        public Individuo Solve(int populacao, int fitness, int geracoes, int crossover, int mutacao, int tipo)
        {
            Stopwatch stopWatch = new Stopwatch();
            stopWatch.Start();

            this.GerarPopulacao(populacao, 56, 56);
            //this.Populacao.RemoveAt(0);
            //this.Populacao.Insert(0, MazeHelper.StringToByte("010100000001010101101010010000000000010100000011000100"));
            List<Individuo> HPopulacao = this.Populacao;

            Individuo menor;

            menor = this.CalculaFitness();
            if (MazeDebug.Geracao)
            {
                MazeDebug.WriteLine("[POPULACAO GERADA]");
                MazeDebug.Populacao(HPopulacao);
            }

            int g = 0;
            int f = menor.Fitness;

            while(g < geracoes && f >= fitness)
            {
                //SORTEIO
                if (tipo == 0)
                {
                    HPopulacao = this.SelecaoTorneio();
                }
                else if (tipo == 1)
                {
                    HPopulacao = this.SelecaoRoleta();
                }
                else
                {
                    HPopulacao = this.SelecaoRanking();
                }
                
                //CROSSOVER - retorna filhos
                List<Individuo> HFilhos = this.AplicaCrossOver(HPopulacao, crossover);

                //MUTAÇÃO
                this.AplicarMutacao(HFilhos, mutacao);

                //Junto populacao da selecao e filhos mutados
                HPopulacao.AddRange(HFilhos);
                this.Populacao = HPopulacao;

                //FITNESS (recalculo)
                menor = this.CalculaFitness();
                f = menor.Fitness;

                //Elitismo
                this.Populacao = this.Elitismo(this.Populacao);

                if (MazeDebug.Geracao)
                {
                    MazeDebug.WriteLine(String.Format("[POPULACAO - {0} ]", g));
                    MazeDebug.Populacao(this.Populacao);
                }

                g++;
            }

            if (MazeDebug.Melhor)
            {
                MazeDebug.WriteLine("[MENOR / MELHOR]");
                MazeDebug.WriteLine(String.Format("Gerações: {0}", g));
                MazeDebug.Individuo(menor);
            }

            stopWatch.Stop();
            TimeSpan ts = stopWatch.Elapsed;
            string elapsedTime = String.Format("{0:00}:{1:00}:{2:00}.{3:00}", ts.Hours, ts.Minutes, ts.Seconds, ts.Milliseconds / 10);

            MazeDebug.WriteLine("Tempo: " + elapsedTime);

            return menor;
        }
    }
}
